package pwd.allen;

/**
 * 堆排序：堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。
 * 原理：
 *  把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换....
 *  如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。
 *
 * 时间复杂度：
 *  平均：O(nlog2n) 最坏：O(nlog2n) 最好：O(nlog2n)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 */
public class HeapSort {

    public void sortHeap(int[] array) {
        for (int x = array.length; x > 1; x--) {
            // 对未排序序列建立大顶堆，此时对顶是最大的元素
            buildMaxHeap(array, x);
            //交换堆顶和最后一个元素
            swap(array, 1, x);
        }
    }

    /**
     * 对数组的第一个 结点到第lastIndex个结点建大顶堆
     *
     * @param array
     * @param lastIndex
     */
    private void buildMaxHeap(int[] array, int lastIndex) {
        //从第lastIndex个节点处的父节点开始
        for (int x = lastIndex / 2; x >= 1; x--) {
            //k保存正在判断的结点
            int k = x;
            //如果当前k节点的子节点存在
            while (2 * k <= lastIndex) {
                //biggerIndex保存k结点的左子节点的索引
                int biggerIndex = 2 * k;
                if (biggerIndex < lastIndex) {
                    // 有右子节点
                    if (array[biggerIndex] > array[biggerIndex - 1]) {
                        biggerIndex++;
                    }
                }
                if (array[k - 1] < array[biggerIndex - 1]) {
                    swap(array, k, biggerIndex);
                    k = biggerIndex;
                } else {
                    break;
                }
            }
        }
    }

    private void swap(int[] array, int x, int y) {
        int temp = array[x - 1];
        array[x - 1] = array[y - 1];
        array[y - 1] = temp;
    }

}